Web log de Serge Boisse
On line depuis 1992 !
Résumé : implémentation d'un arbre en js.
Un arbre est une structure de données constituée d'un ensemble de nœuds liés qui représentent une structure arborescente hiérarchique. Chaque nœud est lié aux autres par une relation parent-enfant. Le premier nœud de l'arbre est la racine, tandis que les nœuds sans enfant sont les feuilles.
Chaque nœud d'une structure de données arborescente doit avoir les propriétés suivantes :
key: La clef du nœud (par exemple un entier) doit être unique pour permettre d'adresser ou supprimer un noeud ou ses enfantsvalue: La valeur of the nœudparent: Le parent du nœud (null si non existant)children: Un tableau de pointeurs vers les enfants du nœudLes principales opérations sur cette structure de données arborescente sont :
insert : Insère un nœud comme enfant du nœud parent donné.remove : Supprime un nœud et ses enfants de l'arbre.find : Récupère un nœud donnépreOrderTraversal : Traverse l'arbre en parcourant récursivement chaque nœud suivi de ses enfants.postOrderTraversal : Traverse l'arbre en parcourant récursivement les enfants de chaque nœud, suivis du nœud.class TreeNode {
constructor(key, value = key, parent = null) {
this.key = key;
this.value = value;
this.parent = parent;
this.children = [];
}
get isLeaf() {
return this.children.length === 0;
}
get hasChildren() {
return !this.isLeaf;
}
}
class Tree {
constructor(key, value = key) {
this.root = new TreeNode(key, value);
}
*preOrderTraversal(node = this.root) {
yield node;
if (node.children.length) {
for (let child of node.children) {
yield* this.preOrderTraversal(child);
}
}
}
*postOrderTraversal(node = this.root) {
if (node.children.length) {
for (let child of node.children) {
yield* this.postOrderTraversal(child);
}
}
yield node;
}
insert(parentNodeKey, key, value = key) {
for (let node of this.preOrderTraversal()) {
if (node.key === parentNodeKey) {
node.children.push(new TreeNode(key, value, node));
return true;
}
}
return false;
}
remove(key) {
for (let node of this.preOrderTraversal()) {
const filtered = node.children.filter(c => c.key !== key);
if (filtered.length !== node.children.length) {
node.children = filtered;
return true;
}
}
return false;
}
find(key) {
for (let node of this.preOrderTraversal()) {
if (node.key === key) return node;
}
return undefined;
}
}
Ce code
TreeNode avec un constructor qui initialise les valeurs key, value, parent and children du nœud.isLeaf , qui utilise Array.prototype.length pour vérifier si la liste des enfants children est videhasChildren , qui est l'inverse de isLeaf.Tree avec un constructor qui initialise la racine root de l'arbrepreOrderTraversal() qui traverse l'arbre en pré-ordre, en utilisant la syntaxe yield* pour déléguer récursivement la traversée à lui-même.postOrderTraversal() qui traverse l'arbre en post-ordre,r, en utilisant lui aussi la syntaxe yield*insert() qui ajoute un nouveau noeud à l'arbreremove() qui retire un noeud de l'arbre.find() qui utilise la méthode preOrderTraversal() pour récupérer le nœud dans l'arbre par sa clef.const tree = new Tree(1, 'AB');
tree.insert(1, 11, 'AC');
tree.insert(1, 12, 'BC');
tree.insert(12, 121, 'BG');
[...tree.preOrderTraversal()].map(x => x.value);
// ['AB', 'AC', 'BC', 'BCG']
tree.root.value; // 'AB'
tree.root.hasChildren; // true
tree.find(12).isLeaf; // false
tree.find(121).isLeaf; // true
tree.find(121).parent.value; // 'BC'
tree.remove(12);
[...tree.postOrderTraversal()].map(x => x.value);
// ['AC', 'AB']
Commentaires (0) :
Page :Ajouter un commentaire (pas besoin de s'enregistrer)
En cliquant sur le bouton "Envoyer" vous acceptez les conditions suivantes : Ne pas poster de message injurieux, obscène ou contraire à la loi, ni de liens vers de tels sites. Respecter la "netiquette", ne pas usurper le pseudo d'une autre personne, respecter les posts faits par les autres. L'auteur du site se réserve le droit de supprimer un ou plusieurs posts à tout moment. Merci !Ah oui : le bbcode et le html genre <br>, <a href=...>, <b>b etc. ne fonctionnent pas dans les commentaires. C'est voulu.